package com.leetcode.动态规划;

import java.util.Arrays;

public class L279完全平方数 {
	public static void main(String[] args) {
	}
}

class Sulotion279 {
	public int numSquares(int n) {
		//对于一个正整数n，一定可以表示为若个完全平方数之和。
		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for(int i = 1;i * i <= n;i++) {
			for(int j = i * i;j <= n;j++) {
				//if(dp[j - i * i] != Integer.MAX_VALUE) 这个判断可以省略
				dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
			}
		}
		return dp[n];
	}
}